﻿using System;

class PrimeNumbersSieveOfEratosthenes
{
    static void Main()
    {
        //Exercise 15.
        //Write a program that finds all prime numbers in the range [1...10 000 000]. 
        //Use the sieve of Eratosthenes algorithm (find it in Wikipedia).

        bool[] array = new bool[10000000];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = true;
        }

        int max = (int)Math.Sqrt(array.Length);

        for (int i = 2; i <= max; i++)
        {
            if (array[i])
            {
                for (int j = i * i; j < array.Length; j = j + i)
                {
                    array[j] = false;
                }
            }
        }

        for (int i = 2; i < array.Length; i++)
        {
            if (array[i])
            {
                Console.WriteLine(i + " ");
            }
        }
    }
}

